/*
 *修改二分查找算法，使之总是返回和被查找的键匹配的索引最小的元素（且仍然能够保证对数 级别的运行时间）
 */

#include<iostream>
#include<vector>

using namespace std;

int BinarySearch(const vector<int> &nums,int target)
{
    decltype(nums.size()) lo=0;
    decltype(nums.size()) hi=nums.size()-1;
    while(lo<=hi){
        int mid=(lo+hi)/2;//取中间数
        if(nums[mid]==target)//找到
        {
            while(mid!=0&&nums[mid]==nums[mid-1])//由于有序 看是否有相同的
            {
                --mid;
            }
            return mid;
        }
        if(nums[mid]>target)
            hi=mid-1;
        else
            lo=mid+1;
    }
    return -1;//没找到
}
int main()
{

}